//54.螺旋矩阵
//https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-100-liked
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int up = 0; //上区间
        int left = 0; //左区间
        int right = matrix[0].size() - 1; //右区间
        int low = matrix.size() - 1; //下区间

        int num = matrix[0].size() * matrix.size();
        vector<int> ret;
        ret.reserve(num);
        while (up <= low && left <= right)
        {
            //从左到右
            for (int i = left; i <= right && ret.size() < num; ++i) ret.push_back(matrix[up][i]);
            ++up;
            for (int i = up; i <= low && ret.size() < num; ++i) ret.push_back(matrix[i][right]);
            --right;
            for (int i = right; i >= left && ret.size() < num; --i) ret.push_back(matrix[low][i]);
            --low;
            for (int i = low; i >= up && ret.size() < num; --i) ret.push_back(matrix[i][left]);
            ++left;
        }
        return ret;
    }
};